package week01

// 239. 滑动窗口最大值
// https://leetcode-cn.com/problems/sliding-window-maximum/

// 单调队列

// 队列里面存的是下标，不要把下标当做 num 做对比....

func maxSlidingWindow(nums []int, k int) []int {
	var queue []int
	var ans []int
	for i := 0; i < len(nums); i++ {
		for len(queue) > 0 && queue[0] <= i-k {
			queue = queue[1:]
		}
		for len(queue) > 0 && nums[queue[len(queue)-1]] < nums[i] {
			queue = queue[:len(queue)-1]
		}
		queue = append(queue, i)
		if i >= k-1 {
			ans = append(ans, nums[queue[0]])
		}
	}
	return ans
}